小小郭說得對，想要推銷演算法的解題思維，沒有故事是不行的。唯有用故事作為媒介，才能讓大家更有興致地享受演算法解題帶來的樂趣。

嗨大家好，我是卡卡恩，一個演算法理論宅。會一點點數學、會一點點演算法，喜歡分析演算法的時間複雜度，最喜歡圖論和動態規劃。寫程式可以將處理萬物的流程自動化，而學習演算法則可以讓自動化的流程變得更順暢。

高中的時候，如果說大家平常碰面吃飯聊天第一句話『最近過得如何？在忙什麼呢？』那麼我的第一句話大概會脫口而出『要不要聽一個小品演算法題目？給你 N 個數字⋯⋯』這時候，大概會有七、八成的機率整頓飯局就沒我的事了。如果把這件事情建模成一個無記憶化的馬可夫鏈，那麼唯一的穩定態就是『噢，這題真有趣呢，太卡了，先把飯吃完吧』。

程式解題競賽，其實是資訊領域中一個非常偏頗的角落。但是不能否認地，這個角落孕育出了非常多厲害的演算法、以及好實作又有效率的資料結構。你可以把他想像成 Leetcode 題目的艱難版：必須要在極短的時間內設計出演算法、資料結構並寫出正確的程式碼。接下來的三十天，我想要跟大家分享，在人生各個階段，你能夠參加到的各式各樣的程式解題競賽。如果我有參加的話也會順便分享一下當年參加的過程和我覺得有趣的內容。時至今日，程式競賽的資源也比當年多了非常多，所以語句中難免偶有老派或過時的資訊，還請大家不吝指教與海涵。

說到高中生的程式解題競賽，最著名的應該就是國際資訊奧林匹亞 (International Olympiad in Informatics) 了吧。與數學、物理、化學、生物等學科並列，是數一數二早創立而且參賽國家數量也相當多的競賽。筆者有幸能參加 2007 年在克羅埃西亞舉辦的第十九屆國際資訊奧林匹亞，僥倖擠入前 24 名拿到一塊獎牌，而這幾年台灣的國手們在 IOI 比賽中的表現也都相當強勁。

資訊奧林匹亞的比賽是分兩天進行的。總共有兩場各自五個鐘頭的個人賽。每一個國家至多有 4 位選手能參加比賽。絕大多數的年份中，每一場比賽都分別有三道題目，在沒有意外的情況下，通常前兩題會比第三題簡單一點點。不過其中有幾年，為了鼓勵新加入的參賽國家選手，每一場比賽都有四道題目，額外增加的題目通常對台灣選手來說，都是超級簡單的那種。

至於 IOI 題目的形式嘛...原則上就是寫程式解題決勝負。絕大多數的題目，考的是設計出高效率的演算法與資料結構，並且要在百分之百回答正確的情形下，把它實作出來。也有少數的題目會根據你程式的輸出優劣給予部分分數。另外也有一些是互動形式的題目，你的程式可以透過呼叫已經寫好的某些 API 來動態取得資訊。

主辦單位要怎麼測試你的程式是否正確呢？顯然在比賽期間，並沒有足夠的人力進行 Code Review。所以一般來說都是以事先安排好的 (數十至數百筆) 測試資料進行測試的。為了讓選手們能更著重於題目本身，這幾年的題目都會幫你處理好檔案輸入與輸出，並且提供函式介面。選手們只要撰寫函式內容即可。不過這麼做的壞處就是，使用的程式語言會被侷限。不出所料，這幾年已然成為 C++ 獨霸的局面。至於未來會不會出現 Python, Kotlin 或是 Rust 就讓我們拭目以待吧。

演算法小謎題 01

今天的小謎題是個令人懷念的奶牛題目 (Cow)。正確的翻譯是乳牛，美國的資訊奧林匹亞培訓計畫 (USACO) 在命題的時候常常以乳牛為主角。不過，當年 (2007) 的我們都或多或少受到了劉汝佳的《算法藝術與信息學競賽》一書深深地影響著，因此只要一提到以乳牛為主角的程式解題競賽題目，總是會不小心脫口而出奶牛 (Cow) 與農夫約翰 (Farmer John) 等名字。

題目是這樣子的：農夫約翰有 N 頭牛排成一排，由左而右編號為 1, 2, 3, …, N。每一頭牛 i 有一個與眾不同的高度 a[i]。現在每一頭牛都往右邊看，請找出對於每一個 i，編號為 i 的牛往右邊看第一頭擋住視線 (高度大於 a[i]) 的牛的編號。

如果你是高中生或剛接觸演算法的大學生，可以試著設計出解決上述問題的演算法並且分析其時間複雜度。如果你把這道題目當作 Leetcode easy 來刷，那麼你至少能想到三種以上的解法。此外，你還能想想看，在解決這題以後面試官可能會問什麼樣的 follow-ups、甚至是這題到底在實務上有沒有什麼應用。有什麼想法也歡迎在下面留言討論唷。